# coding=utf-8
'''
并差集算法
'''


class UnionFind:
    nodelist = []

    def __init__(self, node_count: int):
        i = 0
        while i < node_count:
            self.nodelist.append(-1)
            i += 1

    """
    连接两颗树或节点
    """

    def union(self, p: int, q: int):
        if self.connected(p, q):
            return
        if self.nodelist[p] > self.nodelist[q]:
            self.nodelist[q] += self.nodelist[q]
            self.nodelist[p] = q
        else:
            self.nodelist[p] += self.nodelist[p]
            self.nodelist[q] = p

    """
    返回头节点的值
    """

    def find(self, p: int) -> int:
        if self.nodelist[p] > 0:
            return self.find(self.nodelist[p])
        else:
            return p

    """
    判断两个节点是否在同一颗树上
    """

    def connected(self, p: int, q: int) -> bool:
        root_p = self.find(p)
        root_q = self.find(q)
        return root_q == root_p

    """
    子树的高
    """

    def count(self, p: int) -> int:
        if self.nodelist[p] > 0:
            return self.count(self.nodelist[p])
        else:
            return -self.nodelist[p]

    def value(self, p: int) -> int:
        return self.nodelist[p]
